package com.datastructures.search;

/**
 * 插值查找
 * @author MaoLin Wang
 * @date 2019/10/3112:54
 */
public class insertValueSearch {
    public static void main(String[] args) {
        //必须是有序的
        //int[]arr={0,1,2,3,4,5};
        int arr[]=new int[100];
        for (int i=0;i<100;i++){
            arr[i]=i;
        }
        int i = insertValueSearch(arr, 0, arr.length - 1, 2);
        System.out.println(i);
    }

    public static int insertValueSearch(int[]arr, int left, int right, int value){

        int count=0;
        System.out.println("count:"+(++count));
        if (left>right || value<arr[0] ||value>arr[arr.length-1]){
            return -1;
        }

        int mid=left + (right -left) * (value - arr[left]) / (arr[right]- arr[left]);
        int midVal=arr[mid];
        if (value>midVal){
           return insertValueSearch(arr,mid+1,right,value);
        }else if (value<midVal){
            return insertValueSearch(arr,left,mid-1,value);
        }else {
            return mid;
        }
    }
}
